package 剑指offer;

import common.TreeNode;
import common.Node;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2021-11-25 9:31
 * 搜索和回溯
 */
public class day15_34_36_54 {
    /**===========================================================================================================================
     * 剑指 Offer 34. 二叉树中和为某一值的路径
     * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
     * 回溯：
     * 路径：之前选择过的从根节点到当前节点的节点集合
     * 选择列表：左右子树
     * 终止条件：到达叶子节点
     * */
    List<List<Integer>> res34=new ArrayList<>();
    void backtrack34(TreeNode node, int target, LinkedList<Integer> path){
        if (node.right==null&&node.left==null) {
            if (target==0){
                //到达根节点且和恰好为target，加入结果中
                res34.add(new LinkedList<>(path));
            }
            return;
        }
        //做出选择
        if (node.left!=null){
            path.add(node.left.val);
            backtrack34(node.left,target-node.left.val,path);
            path.removeLast();
        }
        if (node.right!=null){
            path.add(node.right.val);
            backtrack34(node.right,target-node.right.val,path);
            path.removeLast();
        }
    }
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root==null) return new LinkedList<>();
        LinkedList<Integer> path=new LinkedList<>();
        path.add(root.val);
        backtrack34(root,target-root.val,path);
        return res34;
    }

    /**===========================================================================================================================
     * 剑指 Offer 36. 二叉搜索树与双向链表
     * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
     * 特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
     * 中序遍历得到从小到大的顺序，记录前驱节点pre和头节点head
     * */
    Node pre,head;
    void MidOrder(Node cur){
        if (cur==null) return;
        //遍历左子树
        MidOrder(cur.left);
        if (pre==null) {
            //前驱为null表示当前节点为头节点
            head=cur;
        } else {
            pre.right=cur;
        }
        cur.left=pre;
        pre=cur;
        MidOrder(cur.right);
    }
    public Node treeToDoublyList(Node root) {
        if (root==null) return null;
        MidOrder(root);
        //将头尾连接，变成循环链表
        head.left=pre;
        pre.right=head;
        return head;
    }


    /**===========================================================================================================================
     * 剑指 Offer 54. 二叉搜索树的第k大节点
     * 给定一棵二叉搜索树，请找出其中第k大的节点。
     * 1、中序遍历得到从小到大顺序，放入数组中
     * 2、中序遍历的倒序，变成从大到小
     * */
    List<Integer> list=new LinkedList<>();
    void MidOrder1(TreeNode root){
        if (root==null)return;
        MidOrder1(root.left);
        list.add(root.val);
        MidOrder1(root.right);
    }
    public int kthLargest1(TreeNode root, int k) {
        if (root==null) return 0;
        MidOrder1(root);
        return list.get(list.size()-k);
    }
    //2
    int res,k;
    void midOrderBack(TreeNode root){
        if (root==null) return;
        midOrderBack(root.right);
        if (k==0) return;
        if (--k==0) res=root.val;
        midOrderBack(root.left);
    }
    public int kthLargest(TreeNode root, int k) {
        this.k=k;
        midOrderBack(root);
        return res;
    }
}
